Прямое произведение графов

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Декартово произведение графов.

Декартово произведение или прямое произведение [1] G H графов G и H — это граф, такой, что

  • множество вершин графа G H — это прямое произведение V(G) × V(H)
  • любые две вершины (u,u') и (v,v') смежны в G H тогда и только тогда, когда
    • либо u=v и u' смежна v' в H
    • либо u' =v' и u смежна v в G.

Декартово произведение может быть распознано эффективно за линейное время[2]. Операция является коммутативной как операция на классах изоморфизмов графов, и более строго, графы G H и H G естественно изоморфны, но операция не является коммутативной как операция на помеченных графах. Операция является также ассоциативной, так как графы (F G) H и F (G H) естественно изоморфны.

Обозначение G × H порой используется и для декартова произведения графов, но чаще оно используется для другой конструкции, известной как тензорное произведение графов. Символ квадратика чаще используется и является недвусмысленным для декартова произведения графов. Он показывает визуально четыре ребра, получающиеся в результате декартова произведения двух рёбер[3]

  • Декартово произведение двух рёбер является циклом с четырьмя вершинами: K2 K2=C4.
  • Декартово произведение K2 и пути является лестницей.
  • Декартово произведение двух путей является решёткой.
  • Декартово произведение n рёбер является гиперкубом:
Таким образом, декартово произведение двух графов гиперкубов является другим гиперкубом — Qi Qj=Qi+j.

Если связный граф является декартовым произведением, его можно разложить единственным образом на произведение простых множителей, графов, которые нельзя разложить на произведение графов [4][5]. Однако, Имрих и Клавжар[6] описали несвязный граф, который можно представить двумя различными путями как декартово произведение простых графов:

(K1 + K2 + K22) (K1 + K23)=(K1 + K22 + K24) (K1 + K2),

где знак плюс означает несвязное объединение, а верхний индекс означает кратное декартово произведение.

Декартово произведение является вершинно-транзитивным графом тогда и только тогда, когда каждое из его множителей является вершинно-транзитивным[7].

Декартово произведение является двудольным тогда и только тогда, когда каждый из его множителей является двудольным. Более обще, хроматическое число декартова произведения удовлетворяет уравнению

χ(G H)=max {χ(G), χ(H)}[8].

Гипотеза Хедетниеми утверждает связанное равенство для тензорного произведения графов. Число независимости декартовых произведений непросто вычислить, но, как показал Визинг[5], число независимости удовлетворяет неравенствам

α(G)α(H) + min{|V(G)|-α(G),|V(H)|-α(H)} ≤ α(G H) ≤ min{α(G) |V(H)|, α(H) |V(G)|}.

Гипотеза Визинга утверждает, что число доминирования декартова произведения удовлетворяет неравенству

γ(G H) ≥ γ(G)γ(H).

Алгебраическая теория графов

[править | править код]

Алгебраическую теорию графов можно использовать для анализа декартова произведения графов. Если граф имеет вершин и матрицу смежности , а граф имеет вершин и матрицу смежности , то матрица смежности декартова произведения двух графов задаётся формулой

,

где означает произведение Кронекера матриц, а означает единичную матрицу[9].

Согласно Имриху и Клавжару[6] декартовы произведения графов определили в 1912 Уайтхед и Рассел. Произведение графов неоднократно переоткрывалось позже, в частности, Гертом Сабидусси[4].

Примечания

[править | править код]
  1. Визинг использовал термин «декартово произведение», в статье «Прямое произведение» то же произведение называется прямым.
  2. (Imrich, Peterin 2007). Для более ранних алгоритмов полиномиального времени см. статью Фейгенбаума, Хершбергерга и Шеффера (Feigenbaum, Hershberger, Schäffer 1985), а также статью Ауренхаммера, Хагауэра и Имриха(Aurenhammer, Hagauer, Imrich 1992).
  3. Hahn, Sabidussi, 1997.
  4. 1 2 Sabidussi, 1960.
  5. 1 2 Визинг, 1963.
  6. 1 2 Imrich, Klavžar, 2000.
  7. Imrich, Klavžar, 2000, с. Theorem 4.19.
  8. Sabidussi, 1957.
  9. Kaveh, Rahami, 2005.

Литература

[править | править код]
  • F. Aurenhammer, J. Hagauer, W. Imrich. Cartesian graph factorization at logarithmic cost per edge // Computational Complexity. — 1992. — Т. 2, вып. 4. — С. 331—349. — doi:10.1007/BF01200428.
  • Joan Feigenbaum, John Hershberger, Alejandro A. Schäffer. A polynomial time algorithm for finding the prime factors of Cartesian-product graphs // Discrete Applied Mathematics. — 1985. — Т. 12, вып. 2. — С. 123—138. — doi:10.1016/0166-218X(85)90066-6.
  • Geňa Hahn, Gert Sabidussi. Graph symmetry: algebraic methods and applications. — Springer, 1997. — Т. 497. — С. 116. — ISBN 978-0-7923-4668-5.
  • Wilfried Imrich, Sandi Klavžar. Product Graphs: Structure and Recognition. — Wiley, 2000. — ISBN 0-471-37039-8.
  • Wilfried Imrich, Sandi Klavžar, Douglas F. Rall. Graphs and their Cartesian Products. — A. K. Peters, 2008. — ISBN 1-56881-429-1.
  • Wilfried Imrich, Iztok Peterin. Recognizing Cartesian products in linear time // Discrete Mathematics. — 2007. — Т. 307, вып. 3—5. — С. 472—483. — doi:10.1016/j.disc.2005.09.038.
  • A. Kaveh, H. Rahami. A unified method for eigendecomposition of graph products // Communications in Numerical Methods in Engineering with Biomedical Applications. — 2005. — Т. 21, вып. 7. — С. 377—388. — doi:10.1002/cnm.753.
  • G. Sabidussi. Graphs with given group and given graph-theoretical properties // Canadian Journal of Mathematics. — 1957. — Т. 9. — С. 515—525. — doi:10.4153/CJM-1957-060-7.
  • G. Sabidussi. Graph multiplication // Mathematische Zeitschrift. — 1960. — Т. 72. — С. 446—457. — doi:10.1007/BF01162967.
  • В. Г. Визинг. Декартово произведение графов // Вычислительные системы. — 1963. — Т. 9. — С. 30—43.